#include <iostream>
#include <unordered_set>
#include <vector>
void backtrace(int i, const std::vector<int> &choices,
               std::vector<bool> &selected, std::vector<int> &state,
               std::vector<std::vector<int>> &res) {
  if (state.size() == choices.size()) {
    res.push_back(state);
    return;
  }
  std::unordered_set<int> duplicated;
  for (int i = 0; i < choices.size(); i++) {
    if (!selected[i] && duplicated.find(choices[i]) == duplicated.end()) {
      state.push_back(choices[i]);
      selected[i] = true;
      duplicated.emplace(choices[i]);
      backtrace(i + 1, choices, selected, state, res);
      // 回溯
      state.pop_back();
      selected[i] = false;
    }
  }
}

std::vector<std::vector<int>> permutation(std::vector<int> &choices) {
  std::vector<bool> selected(choices.size(), false);
  std::vector<int> state;
  std::vector<std::vector<int>> res;
  backtrace(0, choices, selected, state, res);
  return res;
}

int main() {
  std::vector<int> nums{1, 1, 3};
  auto res = permutation(nums);
  for (auto &r : res) {
    for (auto &i : r) {
      std::cout << i << " ";
    }
    std::cout << std::endl;
  }
  return 0;
}